package io.github.handyang.algorithms.sort;

import io.github.handyang.algorithms.base.Stopwatch;
import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

@Slf4j
public class SortCompare {

    private double time(SortAlgorithms algorithms, int[] a) {
        Stopwatch stopwatch = new Stopwatch();

        algorithms.sort(a);

        return stopwatch.elapsedTime();
    }

    private double timeRandomInput(SortAlgorithms algorithms, int[] arr, int T) {
        double total = 0;

        for (int i = 0; i < T; i++) {
            int[] data = Arrays.copyOf(arr, arr.length);
            log.debug("{}: {} arr:{}", algorithms.getClass().getSimpleName(), i, data);

            double time = time(algorithms, data);
            total += time;

            log.info("{}: {} time:{}s", algorithms.getClass().getSimpleName(), i, time);
        }

        return total;
    }

    private int[] generateData(int N) {
        int[] data = new int[N];

        Random random = new Random(System.currentTimeMillis());
        for (int i = 0; i < N; i++) {
            data[i] = random.nextInt(10000000);
        }

        return data;
    }

    public void compare(int N, int T, SortAlgorithms... algorithms) {
        int[] data = generateData(N);

        for (SortAlgorithms algorithm : algorithms) {
            log.info("{}: start", algorithm.getClass().getSimpleName());

            double timeRandomInput = timeRandomInput(algorithm, data, T);

            log.info("{}: total time:{}s", algorithm.getClass().getSimpleName(), timeRandomInput);
            log.info("{}: end\n", algorithm.getClass().getSimpleName());
        }
    }

    @Test
    public void testSelectionVSInsert() {
        compare(10000, 10, new SelectionSortAlgorithms(), new InsertSortAlgorithms());
    }

    @Test
    public void testSelectionVSInsertVSShell() {
        compare(100000, 1, new SelectionSortAlgorithms(), new InsertSortAlgorithms(), new ShellSortAlgorithms());
    }

    @Test
    public void testShellVSMerge() {
        compare(1000000, 1, new ShellSortAlgorithms(), new MergeSortAlgorithms());
    }

    @Test
    public void testShellVSQuick() {
        compare(100000, 10, new ShellSortAlgorithms(), new QuickSortAlgorithms());
    }

    @Test
    public void testHeapVSQuick() {
        compare(100000, 10, new HeapSortAlgorithms(), new QuickSortAlgorithms());
    }

    @Test
    public void testQuickVSThreeWayQuick() {
        //在数据有大量重复（香农信息量）的情况下，三向排序有较好的性能
        compare(1000000, 5, new QuickSortAlgorithms(), new ThreeWayQuickSortAlgorithms());
    }

    @Test
    public void testQuickVSIterationQuick() {
        compare(1000000, 5, new QuickSortAlgorithms(), new IterationQuickSortAlgorithms());
    }

    @Test
    public void testThreeWayQuickVSMerge() {
        compare(1000000, 5, new QuickSortAlgorithms(), new MergeSortAlgorithms());
    }

    @Test
    public void testQuickVSCount() {
        compare(10000000, 5, new QuickSortAlgorithms(), new CountSortAlgorithms());
    }

    @Test
    public void testLSDVSMyLSD() {
        compare(1000000, 5, new LSDRadixSortAlgorithms(), new MyLSDRadixSortAlgorithms());
    }
}
